#include "Main.h"
#include "utils.h"


// Lines which compose
// the shortest way
list<CLine> listline;
list<CLine>::iterator iterline;

// All Polygones 
list<CPolygone> listpoly;
list<CPolygone>::iterator iterpoly;

// Polygone which is beeing drawn
CPolygone actualpoly ;

CNormalAstar *NA = new CNormalAstar() ;

///////////////////////
// Functions
//
////////////////////////
void AddpointToPoly ( HWND hwnd );
void paint          ( HWND hwnd );
void LaunchAstar    ( HWND hwnd );

CNode *Astar( POINT dep , POINT arr );

// To calculate the time elapsed
float  time_elapsedNA = 0.00 ;
float  time_elapsed = 0.00 ;

/////////////////////////////////////////
// WndProc
//
// Message's manager
//
/////////////////////////////////////////
LRESULT CALLBACK WndProc( HWND hwnd     ,
                          UINT iMsg     ,
                          WPARAM wParam ,
                          LPARAM lParam  )                       
{

	switch (iMsg)
	{
		case WM_CREATE:
		{
		return 0;
		}

		case WM_LBUTTONDOWN:
		{
			AddpointToPoly(hwnd);
		return 0;
		}

		case WM_RBUTTONDOWN:
		{
			LaunchAstar(hwnd);
		return 0;
		}

		case WM_PAINT:
		{
			paint(hwnd);
		return 0;
		}

		case WM_COMMAND:
		{

		break;
		}
		case WM_DESTROY:
		{
			PostQuitMessage (0);

		return 0;
		}
	}

return DefWindowProc(hwnd,iMsg,wParam,lParam);
}

////////////////////////////////////////
// WinMain
//
// Main function
////////////////////////////////////////
int WINAPI WinMain( HINSTANCE hInstance      ,
                    HINSTANCE hPrevInstance  ,
                    PSTR szCmdLine           ,
                    int iCmdShow               )
{
	static char   szAppName[] = "ReallyPathfinding";
	HWND          hwnd;
	MSG           msg;
	WNDCLASSEX    wndclass;

	wndclass.cbSize        = sizeof (wndclass);
	wndclass.style         = 0;
	wndclass.lpfnWndProc   = WndProc;
	wndclass.cbClsExtra    = 0;
	wndclass.cbWndExtra    = 0;
	wndclass.hInstance     = hInstance;
	wndclass.hIcon         = LoadIcon(NULL,IDI_APPLICATION);
	wndclass.hCursor       = LoadCursor(NULL, IDC_ARROW);
	wndclass.hbrBackground = (HBRUSH)GetStockObject(WHITE_BRUSH);
	wndclass.lpszMenuName  = NULL;
	wndclass.lpszClassName = szAppName;
	wndclass.hIconSm       = LoadIcon(NULL,IDI_APPLICATION);

	RegisterClassEx(&wndclass);

	hwnd = CreateWindow(
					szAppName,               
					szAppName,               
					WS_OVERLAPPED | WS_SYSMENU,     
					CW_USEDEFAULT,           
					CW_USEDEFAULT,           
					WINDOW_WIDTH,                     
					WINDOW_HEIGHT,                     
					NULL,                    
					NULL,                    
					hInstance,               
					NULL);                   

	ShowWindow(hwnd,iCmdShow);
	UpdateWindow(hwnd);

	while(GetMessage(&msg,NULL,0,0))
	{
		TranslateMessage(&msg);
		DispatchMessage(&msg);
	}

return (int)msg.wParam;
}



///////////////////////////////////////////////////
// CheckAccessiblePoint
//
// Check for accesssible point according to a point
// 
// [return] : the list of accessible point
///////////////////////////////////////////////////
list<POINT> CheckAccessiblePoint(POINT p)
{

	// List of accessibles points
	list<POINT> listpoint;

	list<POINT>::iterator iterpoint;
	list<CPolygone>::iterator iterpoly2 ;
	list<CLine>::iterator iterline;

	// Check in every poly
	for ( iterpoly = listpoly.begin() ; iterpoly != listpoly.end() ; iterpoly++)
	{
	
		// Check all points
		for ( iterpoint = iterpoly->listpoint.begin() ; iterpoint != iterpoly->listpoint.end() ; iterpoint++)
		{
			// collision with other line ?
			bool collision = false ;

			// Make a line between the 2 points
			CLine line ;
			line.makeLine(p,*iterpoint,VISUAL);

			
			// Check with other poly if there is collision
			for ( iterpoly2 = listpoly.begin() ;( collision == false && iterpoly2 != listpoly.end() ) ; iterpoly2++ )
			{
			    // Check all lines of the poly
				for (iterline = iterpoly2->listline.begin() ; ( collision == false && iterline != iterpoly2->listline.end() ) ; iterline++ )
				{

					// if it is a solid line and if there's a collision
					if (iterline->type != 1)
					if ( line.LineCollision(*iterline) == true )
						collision = true ;
					
				}
				
			}

			// if there is no collision
			if ( collision == false)
			{
				// Let's add this point
				listpoint.push_front(*iterpoint);
			}
		}
	}


return listpoint;
}

////////////////////////////////////
// AccessBetweenTwoPoints
//
// Check if there is no obstable between 
// 2 points
//
// [return] true if ther is an obstacle
////////////////////////////////////////
bool AccessBetweenTwoPoints(POINT a , POINT b )
{

	list<CPolygone>::iterator iterpoly2 ;
	list<POINT>::iterator iterpoint;
	list<CLine>::iterator iterline;
	listline.clear();


	// Make a line between the 2 points
	CLine line ;
	line.makeLine(a,b,VISUAL);

			
	// Check with other poly if there is collision
	for ( iterpoly2 = listpoly.begin() ; iterpoly2 != listpoly.end()  ; iterpoly2++ )
	{
	    // Check all lines of the poly
		for (iterline = iterpoly2->listline.begin() ;  iterline != iterpoly2->listline.end()  ; iterline++ )
		{
			// if it is a solid line and if there's a collision
			if (iterline->type != 1)
			if ( line.LineCollision(*iterline) == true )
				return false ;				
		}
				
	}

	return true ;
}

///////////////////////////////////
// LaunchAstar
//
// launch the research of 
// the shortest way between 2 points
/////////////////////////////////////
void LaunchAstar( HWND hwnd )
{

	POINT departure,arrival ;

	departure.x = 10;
	departure.y = 10 ;
			
	arrival.x = 700 ;
	arrival.y = 500 ;

	Timer timer ;

	timer.Start();
	// Take the way
	CNode *node = Astar(departure,arrival);
	time_elapsed = timer.GetElapsedTime();

	CNode *n = node ;
	// build the path with lines
	while(n->parent)
	{
		CLine line ;
		line.makeLine(n->p,n->parent->p,VISUAL);
		listline.push_front(line);

	n = n->parent ;
	}



	NA->PrepareAstar(listpoly);

	timer.Start();
	// Normal pathfinding
	//NA->DoPath(departure,arrival);

	time_elapsedNA = timer.GetElapsedTime();

	
	// Re-Draw	
	InvalidateRect(hwnd, 0, true);

}

///////////////////////////////
// AddpointToPoly
//
// User clicked on left button
///////////////////////////////
void AddpointToPoly( HWND hwnd )
{
	POINT pt;

	GetCursorPos(&pt);
	ScreenToClient(hwnd,&pt);

	actualpoly.AddPoint(pt);

	if ( actualpoly.isComplete() )
	{
		listpoly.push_front(actualpoly);
		actualpoly.clear();
	}

	InvalidateRect(hwnd, 0, true);

}

/////////////////////////////////////
// Paint 
//
// Called when the windows is to paint
//////////////////////////////////////
void paint( HWND hwnd )
{
	HDC		      hdc  ;
	PAINTSTRUCT   ps   ;
	RECT		  rect ;
			
	hdc = BeginPaint(hwnd,&ps) ;
	GetClientRect(hwnd,&rect)  ;

	actualpoly.Draw(hdc);

	for ( iterpoly = listpoly.begin() ; iterpoly != listpoly.end() ; iterpoly++)
	{
		iterpoly->Draw(hdc);
	}

	for ( iterline = listline.begin() ; iterline != listline.end() ; iterline++)
	{
		iterline->Draw(hdc);
	}

	NA->Draw(hdc);

	char chaine[30];
	
	sprintf(chaine,"Normal Astar %0.2f ms",(time_elapsedNA*1000));
	chaine[29] = '\0' ;
	DrawText( hdc, chaine, -1, &rect,   DT_SINGLELINE );

	sprintf(chaine,"Poly Astar %0.2f ms",(time_elapsed*1000));
	chaine[29] = '\0' ;
	DrawText( hdc, chaine, -1, &rect,   DT_CENTER );

	
	EndPaint(hwnd,&ps);
}

// For A* we need an open Node list
//           and a closed Node list
list<CNode> opennode   ;
list<CNode> closenode   ;


///////////////////////////////////////////////
// IsInClose
// 
// Check if a Node is in the close list
// [return] : true if the Node is in the close list
//////////////////////////////////////////////
bool IsInClose(POINT p)
{

	list<CNode>::iterator iternode ;

	for ( iternode = closenode.begin() ; iternode != closenode.end() ; iternode++ )
	{
		if ( iternode->p.x == p.x && iternode->p.y == p.y )
			return true ;
	}


return false ;
}
///////////////////////////////
// GetBetterNode
// 
// Get the node with the lowest
// totalCost
// [return] : the better CNode
///////////////////////////////
CNode *GetBetterNode()
{

	double distmin = 999999 ;
	CNode *best = new CNode() ;

	list<CNode>::iterator iternode;

	for ( iternode = opennode.begin() ; iternode != opennode.end() ; iternode++ )
	{
		if ( iternode->TotalCost < distmin && IsInClose(iternode->p) == false )
		{
			distmin = iternode->TotalCost ;
			best = &*iternode ;
		}

	}

return best ;
}

////////////////////////////////////////////////
// Astar
//
// Search the quickest way between 2 points
//
// [return] : The Node which countains the way
//            in its parent
////////////////////////////////////////////////
CNode *Astar( POINT dep , POINT arr )
{
	// Clear the 2 lists of Nodes
	 opennode.clear();
	closenode.clear();

	// Make the first Node
	// according to the departure point
	CNode *n  = new CNode ;
	n->p = dep            ;
	n->CostFromStart = 0  ;
	n->TotalCost  = CUtils::dist(dep,arr);
	n->parent = NULL ;  

	// Add the first node in the open list
	opennode.push_front(*n);

	// to prevent seeking in vain 
	// if there is no solution
	int max_iteration = 500 ; 

	while ( opennode.empty() == false && max_iteration > 0 )
	{
		// Get the better Point
		CNode *actual = new CNode ; 
		actual = GetBetterNode();

		// If the arrival is reachable
		if ( AccessBetweenTwoPoints(actual->p , arr ) )
		{
			CNode *last = new CNode ;
			last->p = arr ;
			last->CostFromStart = actual->CostFromStart + CUtils::dist(last->p,actual->p);
			last->TotalCost = last->CostFromStart  ;
			last->parent = actual ;
		
			return last ;
		}
		else
		{

			// list of accessibles points from the actual
		    list<POINT> listaccesspoint = CheckAccessiblePoint(actual->p) ;

			list<POINT>::iterator iterpoint ;
			for ( iterpoint = listaccesspoint.begin() ; iterpoint != listaccesspoint.end() ; iterpoint++ )
			{
				if (IsInClose(*iterpoint) == false && 
					iterpoint->y > 0 && iterpoint->y < WINDOW_HEIGHT-20 
					&& iterpoint->x > 0 && iterpoint->x < WINDOW_WIDTH-20 )
				{
					CNode *neighbour = new CNode ;
					neighbour->p = *iterpoint ;
					neighbour->CostFromStart = actual->CostFromStart + CUtils::dist(neighbour->p,actual->p);
					neighbour->TotalCost = neighbour->CostFromStart  + CUtils::dist(neighbour->p,arr);
					neighbour->parent = actual ;

					opennode.push_front(*neighbour);
					delete neighbour ;

				}

			}


		}
		// Add the node in the closed list
		closenode.push_front(*actual);
		// decrement iteration 
		max_iteration--;
		
	}


return n ;
}


